package com.lcm.oj.labuladong.p0.fib;

/**
 * @author Coder-lcm
 * @date 2021/4/5
 */
public class FiberDemo {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
//        System.out.println( fib1(30));
//        System.out.println( fib2(30));
        System.out.println( fib3(100));
        System.out.println("waste time: " + (System.currentTimeMillis() - start));
    }

    public static int fib3(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int a=1,b=1,c=0;
        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    // 使用一个动态规划数组来存储，以减少不必要的运算
    public static int fib2(int n){
        int[] dp = new int[n+1];
        if (n == 1 || n == 2) {
            return 1;
        }
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    // 递归穷举 。 复杂度为2的n次方
    public static int fib1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib1(n-1) + fib1(n-2);
    }
}
